c23b0b4ca1b662493b1646cfe95451df9c485e3c,src/it/unimi/dsi/sux4j/mph/HypergraphSolver.java,HypergraphSolver,directHyperedges,#number[][]#number[]#number[]#number[]#number[]#number[]#number#,507
Before Change
update( queue, posInQueue, priority, v0, update );
}
if ( ! isHinge[ v1 ] ) {
update( queue, posInQueue, priority, v1, update );
}
if ( ! isHinge[ v2 ] ) {
update( queue, posInQueue, priority, v2, update );
}
}
final int v0 = vertex0[ edge ];
final int v1 = vertex1[ edge ];
final int v2 = vertex2[ edge ];
assert hinge == v0 || hinge == v1 || hinge == v2 : hinge + " != " + v0 + ", " + v1 + ", " + v2;
d[ v0 ]--;
if ( ! isHinge[ v0 ] ) {
update2( d, weight, queue, posInQueue, priority, edge, v0 );
}
d[ v1 ]--;
if ( ! isHinge[ v1 ] ) {
update2( d, weight, queue, posInQueue, priority, edge, v1 );
}
d[ v2 ]--;
After Change
*/
public static boolean directHyperedges( int[][] edges , int[] d , int[] vertex0 , int[] vertex1 , int[] vertex2 , int[] hinges ) {
final int numVertices = d.length;
final int numEdges = vertex0.length;
final int[] weight = new int[ numEdges ];
final boolean[] isHinge = new boolean[ numVertices ];
final boolean[] isDone = new boolean[ numEdges ];
Arrays.fill( weight, 3 );
if ( ASSERTS ) {
final int[] testd = new int[ d.length ];
for ( int i = 0; i < numEdges; i++ ) {
testd[ vertex0[ i ] ]++;
testd[ vertex1[ i ] ]++;
testd[ vertex2[ i ] ]++;
}
if ( ! Arrays.equals( testd, d ) ) throw new AssertionError( "Degree array not valid: " + Arrays.toString( testd ) + " != " + Arrays.toString( d ) );
}
/* - queues of index 0,1,..,6 contains vertices with that priority.
* - the queue of index 7 contains all vertices with priority > 6. */
final IntArrayList[] queue = new IntArrayList[ 8 ];
for( int i = queue.length; i-- != 0; ) queue[ i ] = new IntArrayList();
// For each vertex, its position in the queue it lives in.
final int[] posInQueue = new int[ numVertices ];
// Priorities, multiplied by 6 (so they are all integers)
final int[] priority = new int[ numVertices ];
for ( int i = 0; i < numVertices; i++ ) priority[ i ] += 2 * d[ i ];
for ( int i = 0; i < d.length; i++ ) if ( d[ i ] > 0 ) {
final IntArrayList q = queue[ Math.min( 7, priority[ i ] ) ];
posInQueue[ i ] = q.size();
q.add( i );
}
for ( int t = 0; t < numEdges; t++ ) {
// Find hinge by looking at the node with minimum priority
int minPriority = 0;
while( minPriority < 8 && queue[ minPriority ].isEmpty() ) minPriority++;
if ( minPriority == 8 ) return false;
final int hinge = queue[ minPriority ].popInt();
int edge = -1;
int minWeight = Integer.MAX_VALUE;
for( int i = edges[ hinge ].length; i-- != 0; ) {
final int e = edges[ hinge ][ i ];
if ( ! isDone[ e ] && weight[ e ] < minWeight ) {
edge = e;
minWeight = weight[ e ];
}
}
assert edge != -1;
if ( ASSERTS ) {
int minEdgeWeight = Integer.MAX_VALUE;
int minEdge = -1;
for( int i = 0; i < numEdges; i++ ) if ( ! isDone[ i ] ) {
if ( vertex0[ i ] == hinge || vertex1[ i ] == hinge || vertex2[ i ] == hinge ) {
if ( weight[ i ] < minEdgeWeight ) {
minEdgeWeight = weight[ i ];
minEdge = i;
}
}
}
if ( weight[ edge ] != weight[ minEdge ] ) throw new AssertionError( "Min edge " + t + ": " + minEdge + " != " + edge );
}
//System.err.println( "Round " + ( t - offset ) + ": found hinge " + hinge + " for edge " + edge + " (" + vertex0[ edge ] + ", " + vertex1[ edge ] + ", " + vertex2[ edge ] + ")" );
if ( priority[ hinge ] > 6 ) {
//System.err.println( "Hinge " + hinge + " priority: " + priority[ hinge ] );
return false;
}
hinges[ edge ] = hinge;
isHinge[ hinge ] = true;
isDone[ edge ] = true;
for( int i = edges[ hinge ].length; i-- != 0; ) {
final int e = edges[ hinge ][ i ];
if ( isDone[ e ] ) continue;
final int v0 = vertex0[ e ];
final int v1 = vertex1[ e ];
final int v2 = vertex2[ e ];
assert hinge == v0 || hinge == v1 || hinge == v2 : hinge + " != " + v0 + ", " + v1 + ", " + v2;
final int update = -6 / weight[ e ] + 6 / --weight[ e ];
if ( ! isHinge[ v0 ] ) increase( queue, posInQueue, priority, v0, update );
if ( ! isHinge[ v1 ] ) increase( queue, posInQueue, priority, v1, update );
if ( ! isHinge[ v2 ] ) increase( queue, posInQueue, priority, v2, update );
}
final int v0 = vertex0[ edge ];
final int v1 = vertex1[ edge ];
final int v2 = vertex2[ edge ];
assert hinge == v0 || hinge == v1 || hinge == v2 : hinge + " != " + v0 + ", " + v1 + ", " + v2;
d[ v0 ]--;
if ( ! isHinge[ v0 ] ) decrease( queue, posInQueue, priority, d, v0, weight[ edge ] );
d[ v1 ]--;
if ( ! isHinge[ v1 ] ) decrease( queue, posInQueue, priority, d, v1, weight[ edge ] );